package hot100;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

public class TopKFrequent {
    public int[] topKFrequent(int[] nums, int k) {
        //先将每个数字出现的次数整理出来
        Map<Integer,Integer> map = new HashMap<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int curCount = map.getOrDefault(nums[i],0);
            map.put(nums[i],curCount + 1);
        }

        Set<Integer> keys = map.keySet();
        Integer[] distinct = keys.toArray(new Integer[0]);

        //堆排序
        heapSort(distinct,map);

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = distinct[distinct.length - 1 - i];
        }

        return res;
    }

    private void heapSort(Integer[] distinct, Map<Integer, Integer> map) {
        int n = distinct.length;
        //建堆
        buildHeap(distinct,map);
        //去排序
        for (int i = n - 1; i > 0; i--) {
            swap(distinct,0,i);
            heapify(distinct,map,i,0);
        }
    }

    private void buildHeap(Integer[] distinct, Map<Integer, Integer> map) {
        int n = distinct.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(distinct,map,n,i);
        }
    }

    private void heapify(Integer[] distinct, Map<Integer, Integer> map, int n, int i) {
        int largest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;

        if (left < n && map.get(distinct[left]) > map.get(distinct[largest])) largest = left;
        if (right < n && map.get(distinct[right]) > map.get(distinct[largest])) largest = right;

        if (largest != i) {
            swap(distinct,largest,i);
            heapify(distinct,map,n,largest);
        }
    }

    private void swap(Integer[] distinct, int index1, int index2) {
        int temp = distinct[index1];
        distinct[index1] = distinct[index2];
        distinct[index2] = temp;
    }

    @Test
    public void test() {
        int[] nums = {5,2,5,3,5,3,1,1,3};
        int[] ints = topKFrequent(nums, 2);
        System.out.println();
    }
}
